Characterizing Minimal Semantics-preserving Slices of predicate-linear, Free, Liberal Program Schemas

摘要

A program schema defines a class of programs, all of which have identicalstatement structure, but whose functions and predicates may differ. A schemathus defines an entire class of programs according to how its symbols areinterpreted. A subschema of a schema is obtained from a schema by deleting someof its statements. We prove that given a schema $S$ which is predicate-linear,free and liberal, such that the true and false parts of every if predicatesatisfy a simple additional condition, and a slicing criterion defined by thefinal value of a given variable after execution of any program defined by $S$,the minimal subschema of $S$ which respects this slicing criterion contains allthe function and predicate symbols `needed' by the variable according to thedata dependence and control dependence relations used in program slicing, whichis the symbol set given by Weiser's static slicing algorithm. Thus thisalgorithm gives predicate-minimal slices for classes of programs represented byschemas satisfying our set of conditions. We also give an example to show thatthe corresponding result with respect to the slicing criterion defined bytermination behaviour is incorrect. This complements a result by the authors inwhich $S$ was required to be function-linear, instead of predicate-linear.